package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/tool"
)

func main() {
	n1 := ListNode{Val: 1}
	n2 := ListNode{Val: 2}
	n3 := ListNode{Val: 3}
	n4 := ListNode{Val: 5}
	n5 := ListNode{Val: 9}
	n1.Next = &n2
	n2.Next = &n3
	n3.Next = &n4
	n4.Next = &n5
	n11 := ListNode{Val: 2}
	n21 := ListNode{Val: 5}

	n11.Next = &n21

	lists := MergeTwoLists(&n1, &n11)

	fmt.Println(lists)
}

func MergeTwoLists(l1, l2 *ListNode) *ListNode {
	var cur *ListNode //两个指针用来指向
	var cur1 *ListNode
	var pre *ListNode
	var head *ListNode
	if l1 == nil {
		return l2
	} else if l2 == nil {

		return l1
	}

	if l1.Val < l2.Val {
		head = l1

		cur = head.Next
		cur1 = l2
	} else {
		head = l2
		cur = head.Next
		cur1 = l1
	}
	pre = head
	for cur != nil && cur1 != nil {

		if cur.Val < cur1.Val {
			pre.Next = cur

			cur = cur.Next
		} else if cur1.Val < cur.Val {
			pre.Next = cur1
			cur1 = cur1.Next
		} else if cur1.Val == cur.Val {
			pre.Next = cur
			cur = cur.Next
		}
		pre = pre.Next

	}
	if cur != nil {
		pre.Next = cur

	} else if cur1 != nil {
		pre.Next = cur1

	}
	return head
}
